/*
 *  HeapPQueue.cpp
 *  project2
 *
 *  Created by Maria Piao on 09-10-11.
 *
 */


#ifndef _HEAPPQUEUE_CPP
#define _HEAPPQUEUE_CPP

#include <iostream>
#include "HeapPQueue.h"

using namespace std;

//Constructor
template <class Object, class Compare>
HeapPQueue<Object, Compare>::HeapPQueue(int aArity){
	if (aArity > 0){
		arity = aArity; //assign the degree of the tree to specified
	} else {
		arity = 2;
	}
}

//Destructor
template <class Object, class Compare>
HeapPQueue<Object, Compare>::~HeapPQueue() {
	makeEmpty(); //delete all the element in the heap
	//(vector)heap itself is a static variable, therefore does not need to be deleted
}

//return true if the array is empty
template <class Object, class Compare>
bool HeapPQueue<Object, Compare>::isEmpty() const{
	return heap.empty(); //if the vector is empty, the heap is empty, the queue is empty
}


template <class Object, class Compare>
const Object& HeapPQueue<Object, Compare>:: findMin() const{
		return heap.front(); //return the first object in vector
}


template <class Object, class Compare>
void HeapPQueue<Object, Compare>::insert(const Object& x){
	heap.push_back(x); //put x into the heap
	percolateUpLastElement(); //now find its proper place
}


template <class Object, class Compare>
void HeapPQueue<Object, Compare>::deleteMin(){
	if (!isEmpty()){
		heap.at(0) = heap.back();//fill up the root with the rightmost leave
		heap.pop_back();//delete the rightmost leave, since it is the root for now
		percolateDownRoot();//make the root go to the right place
	}
}


template <class Object, class Compare>
void HeapPQueue<Object, Compare>::deleteMin(Object& minItem){
	if (!isEmpty()){
		minItem = findMin();
		deleteMin();
	}
}


template <class Object, class Compare>
void HeapPQueue<Object, Compare>::makeEmpty(){
	heap.clear();//the vector should delete all its element for us.
}

//for debugging
template<class Object, class Compare>
void HeapPQueue<Object, Compare>::printHeap(){
	for (int i = 0; i< heap.size(); i++){
		cout << heap[i] <<endl;
	}
}

//make sure the last element is in its proper place
template <class Object, class Compare>
void HeapPQueue<Object, Compare>::percolateUpLastElement(){
	percolateUp(heap.size()-1);//find the index of the last element, then delegate to percolateUp
}


template <class Object, class Compare>
void HeapPQueue<Object, Compare>::percolateUp(int index){
	Object childElement = heap.at(index);//this is the index of the child in question
	int parentIndex = (index-1)/arity; //this is the index of the parent
	if (parentIndex < 0){
		return; //if parent index is negative, then the child is the root, just return
	}
	
	Object parentElement = heap.at(parentIndex); //since the parent index is valid, get it
	
	if (!shouldSwap(parentElement, childElement)) {
		return; //the parent and child are in their proper place
	}
	swap(parentIndex, index); //the parent and child violate heap invariant, switch!
	percolateUp(parentIndex); //is the new parents still violating heap invariant?
}

template <class Object, class Compare>
void HeapPQueue<Object, Compare>::percolateDownRoot(){
	percolateDown(0);
}

template <class Object, class Compare>
void HeapPQueue<Object, Compare>::percolateDown(int index){	
	if (index*arity+1 >= (int)heap.size()) {//bound checking
		//this is a leaf
		return;
	}
	
	//If we get here, then the index must have at least one child. Hence no bound checking needed
	int maxChildIndex = index*arity+1; //initialize max child to be the first child
	Object maxChild = heap.at(maxChildIndex);
	
	int currentChildIndex;
	
	for(int i = 2; i<= arity; i++){
		currentChildIndex = index*arity+i;
		//check bound
		if(currentChildIndex < (int)heap.size()){
			//If the max child is smaller than current child
			if (shouldSwap(maxChild, heap.at(currentChildIndex))){
				//max child is now current child
				maxChild = heap.at(currentChildIndex);
				maxChildIndex = currentChildIndex;
			}
		}
	}
	
	if (shouldSwap(heap.at(index), maxChild)){
		swap(index, maxChildIndex);
	}
	percolateDown(maxChildIndex);
}

//return true if the first element(parent) is lower priority than the second element(child);
template <class Object, class Compare>
bool HeapPQueue<Object, Compare>::shouldSwap(Object parent, Object child){
	return comp(parent, child);
}

//standard swap operation
template <class Object, class Compare>
void HeapPQueue<Object, Compare>::swap(int index1, int index2) {
	Object temp = heap.at(index1);
	heap[index1] = heap.at(index2);
	heap[index2] = temp;
}

template <class Object, class Compare>
void HeapPQueue<Object, Compare>::printTypeName(){
	cout<<"Priority Queue with Heap of degree "<<arity;
}

template <class Object, class Compare>
int HeapPQueue<Object, Compare>::getNumberOfElements(){
	return heap.size();
}
#endif
